package snippet;
import java.util.*;
public class 分割回文串 {
	List<List<String>> result = new ArrayList<>();
	List<String> item = new ArrayList<>();
	StringBuilder stb;
	
    public List<List<String>> partition(String s) {
    	backtracking(s,0);
//    	System.out.println(result.size());
//    	System.out.println(result);
    	return result;
    }
    
    public void backtracking(String s, int index) {
    	if(index == s.length()) {
    		result.add(new ArrayList<>(item));
    		return;
    	}
    	
    	for(int i = index; i < s.length(); i++) {
    		stb = new StringBuilder(s.substring(index, i + 1));
        	if(stb.reverse().toString().equals(stb.reverse().toString()) && !stb.toString().isEmpty()) {
        		item.add(stb.toString());
        	} else {
        		continue;
        	}
    		backtracking(s, i+1);
    		item.remove(item.size() - 1);
    	}

    }
    
	public static void main(String[] args) {
		new 分割回文串().partition("a");
	}
}
